import random

# 初始化种群
def initialize_population(num_chromosomes, num_customers):
    population = []
    for _ in range(num_chromosomes):
        chromosome = list(range(1, num_customers + 1))
        random.shuffle(chromosome)
        population.append(chromosome)
    return population

# 计算适应度函数（简单示例，可根据实际需求修改）
def fitness_function(chromosome):
    # 这里简单返回路径长度的倒数作为适应度值
    path_length = sum([abs(chromosome[i] - chromosome[i + 1]) for i in range(len(chromosome) - 1)])
    return 1 / path_length

# 选择操作（轮盘赌选择）
def selection(population):
    fitness_values = [fitness_function(chromosome) for chromosome in population]
    total_fitness = sum(fitness_values)
    probabilities = [fitness / total_fitness for fitness in fitness_values]
    selected_index = random.choices(range(len(population)), weights=probabilities)[0]
    return population[selected_index]

# 交叉操作（单点交叉）
def crossover(parent1, parent2):
    crossover_point = random.randint(1, len(parent1) - 1)
    child1 = parent1[:crossover_point] + [gene for gene in parent2 if gene not in parent1[:crossover_point]]
    child2 = parent2[:crossover_point] + [gene for gene in parent1 if gene not in parent2[:crossover_point]]
    return child1, child2

# 变异操作（交换变异）
def mutation(chromosome):
    index1, index2 = random.sample(range(len(chromosome)), 2)
    chromosome[index1], chromosome[index2] = chromosome[index2], chromosome[index1]
    return chromosome

# 遗传算法主函数
def genetic_algorithm(num_chromosomes, num_customers, num_generations):
    population = initialize_population(num_chromosomes, num_customers)
    for _ in range(num_generations):
        new_population = []
        for _ in range(num_chromosomes // 2):
            parent1 = selection(population)
            parent2 = selection(population)
            child1, child2 = crossover(parent1, parent2)
            child1 = mutation(child1)
            child2 = mutation(child2)
            new_population.extend([child1, child2])
        population = new_population
    best_chromosome = max(population, key=fitness_function)
    return best_chromosome

# 示例调用
num_chromosomes = 50
num_customers = 10
num_generations = 100
best_path = genetic_algorithm(num_chromosomes, num_customers, num_generations)
print("最优路径:", best_path)
